Bitap algorithm
bit-parallel approximate pattern matching
検索文字列長が計算機で表現可能なビット数に制限されるという欠点がある
まあ64文字(=64bit)あれば普通は十分だろう
複数のビット列に分割すれば任意長文字列に対応できないこともない
特徴
pros
一回だけ検索対象文字列を走査すればいい
後戻りすることがない
マッチ判定を並列実行できるとこがミソ
複数のマッチ判定情報を一つのレジスタに重ね合わせて格納している
ビット演算で全てのマッチ判定を一度に行える
すこし計算式をいじることで、一部の文字を編集距離計算から除外する事も出来る
ワイルドカードを実現できる
cons
マッチした位置なら計算できる
部分完全一致検索はマッチしたときの遷移数から計算できる
曖昧検索だと後戻りが発生する
それ以上は「$ n+1以上離れている」ということしかわからなくなる
いろんな名前がある
使っている演算方法の違い
双対性から、AND演算とOR演算のどちらでも実装できる algorithmの流れ
shift-and型を使って解説する
遷移方向は右向きとする
最上位ビットから開始する
ビットが立っている場所は、検索パターンのうちその位置までの部分文字列と一致した箇所があることを示してしている
たとえば検索パターンabcdeである文字列を検索している際に01100というレジスタに状態遷移したら、そこまでの状態遷移でabとabcにマッチする箇所が検索対象文字列から見つかったということになる
曖昧検索の場合は、それぞれのレジスタが担当する距離以内で見つかった検索パターンの部分文字列を表す
たとえば検索パターンabcdeで次のレジスタに遷移したとする
距離2: 01111
距離1: 01110
距離0: 00100
これは、完全一致でabc、距離1以内でabとabcとabcd、距離2以内でabcとabcdとabcdeが検索対象文字列から見つかったことを表している
状態遷移とビット演算との対応
このような流れでマッチ判定する
n+1番目が完全一致
1. n+1回目に遷移可能な位置にビットをたてる
n回遷移したレジスタを1回右シフトする
後方一致も含めるなら、最初のビットをたてておく
ORするだけ
2. 入力する文字が入りうる場所だけビットをたてる
n+1番目に一文字追加
1. 入力された文字を飛ばす
n回遷移したレジスタをそのまま次のレジスタとして扱う
2. 距離を1つ増やす
担当する距離が一つ多いレジスタにORで合成する
n+1番目が一文字置換
1. 完全一致1.と同じ手順を踏む
n+1回目に遷移可能な位置全てに遷移したと考える
2. 距離を1つ増やす
n+2番目が一文字削除
1. n+1回遷移したレジスタから遷移可能な全ての位置にビットをたてる
n+2回目の遷移をする前に、すでにn+2回目に遷移可能な全ての位置に遷移したと見なす
2. 距離を1つ増やす
これでn+2回目以降で判定する文字番号を一つ早めることができる
初期状態は常に1が立つとわかっているので、レジスタに加える必要はない
asearchの実装だと加えてしまっているので、検索パターンに使える最大文字列長が1文字分少ない 実装
2021-10-09 19:12:11 ようやく仕組みを理解しはじめた
あとで解説を書く
References
部分完全一致検索、正規表現に拡張した検索algorithmまで解説されている
ちゃんと文章読んだら、これが一番詳しい解説だと気づいた
benchmarkあり
参考文献リストがある